#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//#include<vector>
//#include<string>
//#include<queue>
//#include<bitset>
//#include<unordered_set>
//#include<functional>
//using namespace std;
//struct Node
//{
//	int value;
//	Node* left;
//	Node* right;
//	Node(int x)
//		:value(x), left(nullptr), right(nullptr)
//	{}
//};
//Node* BuildTree(vector<int>::iterator inleft, vector<int>::iterator inright, vector<int>::iterator postleft, vector<int>::iterator postright)
//{
//	if (postleft >= postright)
//		return nullptr;
//	int value = *(postright - 1);
//	Node* root = new Node(value);
//	vector<int>::iterator mid = find(inleft, inright, value);
//	root->left = BuildTree(inleft, mid, postleft, postleft + (mid - inleft));
//	root->right = BuildTree(mid + 1, inright, postleft + (mid - inleft), postright - 1);
//	return root;
//}
//void Preorder(Node* root)
//{
//	if (root == nullptr)
//		return;
//	ret.push_back(root->value);
//	Preorder(root->left);
//	Preorder(root->right);
//}
//vector<int> ret;
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> inorder(n), postorder(n);
//	for (int i = 0; i < n; i++)
//		cin >> postorder[i];
//	for (int i = 0; i < n; i++)
//		cin >> inorder[i];
//	Node* root = BuildTree(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
//	cout << "Preorder:";
//	Preorder(root);
//	int k = ret.size();
//	int cur = 0;
//	for (; cur < k - 1; cur++)
//	{
//		cout << ret[cur] << " ";
//	}
//	cout << ret[cur];
//	return 0;
//}
//#include <iostream>
//#include <vector>
//#include<string>
//#include<functional>
//#include<queue>
//using namespace std;
//struct Node
//{
//	int value;
//	Node* left, *right;
//	Node(int x)
//		:value(x),left(nullptr),right(nullptr)
//	{}
//
//};
//int main()
//{
//	int n;
//	cin >> n;
//	vector<pair<char, char>> info(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> info[i].first >> info[i].second;
//		getchar();
//	}
//	vector<bool> isHead(n, true);
//	for (int i = 0; i < n; i++)
//	{
//		if (info[i].first != '-')
//			isHead[info[i].first - '0'] = false;
//		if (info[i].second != '-')
//			isHead[info[i].second - '0'] = false;
//	}
//	int head;
//	for (int i = 0; i < n; i++)
//	{
//		if (isHead[i])
//		{
//			head = i;
//			break;
//		}
//	}
//	function<Node*(int)> BuildTree = [&](int node)->Node*
//	{
//		Node* newnode = new Node(node);
//		if (info[node].first != '-')
//			newnode->left = BuildTree(info[node].first - '0');
//		if (info[node].second != '-')
//			newnode->right = BuildTree(info[node].second - '0');
//		return newnode;
//	};
//	Node* root = BuildTree(head);
//	vector<int> ret;
//	auto levelorder = [&]()
//	{
//		queue<Node*> q;
//		q.push(root);
//		while (!q.empty())
//		{
//			int sz = q.size();
//			for (int i = 0; i < sz; i++)
//			{
//				auto tmp = q.front();
//				q.pop();
//				if (tmp->left == nullptr && tmp->right == nullptr)
//					ret.push_back(tmp->value);
//				if (tmp->left)
//					q.push(tmp->left);
//				if (tmp->right)
//					q.push(tmp->right);
//			}
//		}
//	};
//	levelorder();
//	int k = ret.size();
//	int i = 0;
//	for (; i < k - 1; i++)
//		cout << ret[i] << " ";
//	cout << ret[i];
//	return 0;
//}

//#include <iostream>
//#include <vector>
//#include<string>
//#include<functional>
//#include<queue>
//using namespace std;
//struct Node
//{
//	int value;
//	Node* left, *right;
//	Node(int x)
//		:value(x),left(nullptr),right(nullptr)
//	{}
//};
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> postorder(n), inorder(n);
//	for (int i = 0; i < n; i++)
//	{
//		cin >> postorder[i];
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cin >> inorder[i];
//	}
//	function<Node*(vector<int>::iterator, vector<int>::iterator, vector<int>::iterator, vector<int>::iterator)>
//		BuildTree = [&](vector<int>::iterator pleft, vector<int>::iterator prigth,
//		vector<int>::iterator ileft, vector<int>::iterator iright )->Node*
//	{
//		if (pleft >= prigth)
//			return nullptr;
//		int value = *(prigth - 1);
//		Node* newnode = new Node(value);
//		auto mid = find(ileft, iright, value);
//		newnode->left = BuildTree(pleft,pleft + (mid-ileft) , ileft, mid);
//		newnode->right = BuildTree(pleft + (mid - ileft), prigth - 1, mid + 1, iright);
//		return newnode;
//	};
//	Node* root = BuildTree(postorder.begin(), postorder.end(), inorder.begin(), inorder.end());
//	vector<int> ret;
//	auto levelorder = [&]()
//	{
//		queue<Node*> q;
//		q.push(root);
//		while (!q.empty())
//		{
//			int sz = q.size();
//			for (int i = 0; i < sz; i++)
//			{
//				auto tmp = q.front();
//				q.pop();
//				ret.push_back(tmp->value);
//				if (tmp->left)
//					q.push(tmp->left);
//				if (tmp->right)
//					q.push(tmp->right);
//			}
//		}
//	};
//	levelorder();
//	int k = ret.size();
//	int i = 0;
//	for (; i < k - 1; i++)
//		cout << ret[i] << " ";
//	cout << ret[i];
//	return 0;
//}

//#include <iostream>
//#include <vector>
//#include<string>
//#include<functional>
//#include<queue>
//using namespace std;
//int main()
//{
//	int n;
//	cin >> n;
//	vector<int> arr(n + 1, 0);
//	for (int i = 1; i <= n; i++)
//		cin >> arr[i];
//	int a, b;
//	cin >> a >> b;
//	if (arr[a]==0) {
//		printf("ERROR: T[%d] is NULL\n", a);
//		return 0;
//	}
//	if (arr[b]==0) {
//		printf("ERROR: T[%d] is NULL\n", b);
//		return 0;
//	}
//	while (a != b) {
//		if (a > b) swap(a, b);
//		b /= 2;
//	}
//	cout << a << ' ' << arr[a];
//	return 0;
//}
